package LimitedTimeGame.Day_0204;

/**
 * @author zxc
 * @date 2023/02/04 15:57
 **/

import java.util.Stack;

/**
 * 题目 ：检查子树
 * 题目详述 ：
 * 检查子树。你有两棵非常大的二叉树：T1，有几万个节点；
 * T2，有几万个节点。设计一个算法，判断 T2 是否为 T1 的子树。
 * 如果 T1 有这么一个节点 n，其子树与 T2 一模一样，则 T2 为 T1 的子树，
 * 也就是说，从节点 n 处把树砍断，得到的树与 T2 完全相同
 *
 * 提示：
 * 树的节点数目范围为[0, 20000]。
 *
 */
public class CheckSubTree {
    /**
     * 思路 ：
     * 即，获取二叉树T1和二叉树T2的中序遍历结果（深度优先搜索），对于其进行相互之间的比较;
     *
     * @param t1
     * @param t2
     * @return
     */
    public boolean checkSubTree(TreeNode t1, TreeNode t2) {
        // 迭代获取 二叉树T1和二叉树T2的中序遍历结果，使用字符串来进行表示;
        String s1 = inOrderTravesal(t1, new StringBuilder(""));
        String s2 = inOrderTravesal(t2, new StringBuilder(""));
        System.out.println("s1 = " + s1 + ", s2 = " + s2);
        int len1 = s1.length();
        int len2 = s2.length();
        System.out.println(len1 + " " + len2);
        // 字符串s1中所截取字符串的首个元素，取值范围[0,len1 - len2]
        // （len1，为字符串s1的长度;len2，为字符串s2的长度;）
        // 字符串s1中截取和字符串s2长度相同的字符串相比较，是否相等;
        for (int i = 0 ; i <= len1 - len2 ; i++){
            if(s1.substring(i , i + len2).equals(s2)){
                return true;
            }
        }
        return false;
    }
    // 深度优先搜索二叉树，获取当前二叉树的中序遍历结果，同时将其以String类型进行返回;
    private String inOrderTravesal(TreeNode node , StringBuilder str) {
        Stack<TreeNode> stack = new Stack<>();
        while(node != null || !stack.isEmpty()){
            while(node != null){
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            str.append(node.val);
            node = node.right;
        }
        return str.toString();
    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
    }
}
